<HTML>
<HEAD>
<title>Enlightened landscape</title>
</head>
<BODY>

<center>
<h1>CEOI 2000 Day 2 Problem 3</h1>
<h1>Enlightened landscape</h1>
</center>

<p>
Consider a landscape composed of connected line segments:

<CENTER><IMG src='image/4.gif'></CENTER>
Above the landscape, <I>N</I> light bulbs are hang at the same height <I>T</I> in 
various horizontal positions. The purpose of these light bulbs is to light 
up the entire landscape. A landscape point is considered lit if it can 
"see" a light bulb directly, that is, if the line segment which links the 
point with a bulb does not contain any other landscape segments point. 

<h2>Task</h2>
Write a program that determines the mi-ni-mum
number of light bulbs that must be switched on in order to illuminate the 
entire landscape.

<h2>Input</h2>
Input file name: <B>LIGHT.IN</B><BR>
<B>Line 1</B>: M
<LI>An integer, the number of landscape height specifications, including 
the first and the last point of the landscape. <BR>
<B>Lines 2..<I>M</I>+1</B>: X<SUB>i</SUB> H<SUB>i</SUB> 
<LI>Two integers, separated by a space: the landscape height H<SUB>i</SUB> 
at horizontal position X<SUB>i</SUB>, 1 &lt;= i &lt;= M; for 1 &lt;= i 
&lt;= M-1 we have X<SUB>i+1</SUB> &gt; X<SUB>i</SUB>; any two consecutive 
specified points identify a segment of line in the landscape. <BR>
<B>Line <I>M</I>+2</B>: N T 
<LI>Two integers, separated by a space, the num-ber of light bulbs and 
their height coordinate (altitude). The bulbs are numbered from 1 to N) <BR>
<B>Line M+3</B>: B<SUB>1</SUB> B<SUB>2</SUB> ... B<SUB>N</SUB>
<LI>N integers, separated by spaces: the hori-zon-tal coordinates of the 
light bulbs Bi+1 &gt; Bi, 1 &lt; i &lt;= N-1;

<h2>Output </h2>
File name: <B>LIGHT.OUT</B> <BR>
<B>Line 1</B>: K
<LI>An integer: the minimum number of light bulbs to be switched on. <BR>
<B>Line 2</B>: L<SUB>1</SUB> L<SUB>2</SUB> ... L<SUB>K</SUB>
<LI>K integers, separated by spaces: the labels of the light bulbs to be 
switched on spe-cified in increasing order of their horizontal 
coordinates.

<h2>Limits</h2>
<LI>1 &lt;= M &lt;= 200 
<LI>1 &lt;= N &lt;= 200 
<LI>1 &lt;= X<SUB>i</SUB> &lt;= 10000 for 1 &lt;= i &lt;= M 
<LI>1 &lt; T &lt;= 10000 
<LI>1 &lt;= H<SUB>i</SUB> &lt;= 10000 for 1 &lt;= i &lt;= M 
<LI>T &gt; H<SUB>i</SUB> for any 1 &lt;= i &lt;= M 
<LI>X<SUB>1</SUB> &lt;= B<SUB>1</SUB> and B<SUB>N</SUB> &lt;=X<SUB>M</SUB> 
<LI>The task always has a solution for the test data. If there are 
multiple solutions, only one is required.

<h2>Sample Input</h2>
<pre>
6
1 1
3 3
4 1
7 1
8 3
11 1
4 5
1 5 6 10
</PRE>

<h2>Sample Output</h2>
<pre>
2
1 4
</pre>

</BODY></HTML>
